#include "LinkTree.h"
#include<iostream>
TreeNode::TreeNode(const ElementType &element)
{
    data=element;
    parent=nextSbling=firstChild=nullptr;
}

void TreeNode::Connect(TreeNode *parent)
{
    if(!parent)//不是双亲返回
        return;
    this->parent=parent;
    this->nextSbling=parent->firstChild;//头插
    parent->firstChild=this;
}

void TreeNode::Disconnect(TreeNode *parent)
{
    if(parent==nullptr&&this->parent!=parent)//双亲指针为空或者我不是双亲的孩子
            return;
    TreeNode *travePoint=parent->firstChild;
    if(this==parent->firstChild)//我是双亲的第一个孩子
        parent->firstChild=this->nextSbling;
    else
    {
        while(travePoint->nextSbling!=nullptr)//遍历找到我的上一个兄弟
        {
            if(travePoint->nextSbling==this)
            {
                travePoint->nextSbling=this->nextSbling;
                break;
            }
            travePoint=travePoint->nextSbling;
        }
    }
    this->parent=this->nextSbling=nullptr;//为避免二次释放，需要从家族中脱离
        
}

LinkTree::LinkTree()
{
    root=new TreeNode(nullptr);//根不能为空
    Free=nullptr;

}

LinkTree::~LinkTree()
{
    FreeNode(root);
}

void LinkTree::show()
{
    show(root,-1);//根节点不算层
}

doubleLinkList LinkTree::FindByelement(const ElementType &element)
{
    doubleLinkList list;
    FindNode(root,element,list);
    return list;
    

}

int LinkTree::GetTreeHeight()
{
   return GetNodeHeight(root)-1;//根节点不算高度
}

int LinkTree::Size()
{
    int count=0;
    GetNodeSize(root,count);
    return count-1;
}

int LinkTree::leafSize()
{
   int count=0;
   GetleafSize(root,count);
   return count;
}

void LinkTree::show(TreeNode *node,int deepth)
{
    if(node==nullptr)//递归终止条件
        return;
    if(node->parent!=nullptr)//不是根节点才打印
    { 
      if(deepth>0)
      {
      for(int i=0;i<deepth-1;i++)
            std::cout<<"  ";
       std::cout<<"|__";
      }
       Print(node->data);
    }       
    //深度优先遍历
    show(node->firstChild,deepth+1);
    show(node->nextSbling,deepth);
    //广度优先
    // show(node->nextSbling);
    // show(node->firstChild);
}

void LinkTree::FreeNode(TreeNode *node)
{
     if(node==nullptr)//递归终止条件
        return;
    FreeNode(node->firstChild);
    FreeNode(node->nextSbling);
    if(Free)
    {
        Free(node->data);
    }
    delete node;//先找到最下层结点，再释放
}

void LinkTree::FindNode(TreeNode* node ,const ElementType &element, doubleLinkList &list)
{
    if(node==nullptr)
        return;
    if(Compare(node->data,element)&&node!=root)
        list.insertTail(node);
    FindNode(node->firstChild,element,list);
    FindNode(node->nextSbling,element,list);
}

int LinkTree::GetNodeHeight(TreeNode *node)
{
   if(node==nullptr)
        return 0;
    int MaxHeight=0;
    TreeNode *travePoint=node->firstChild;
    while(travePoint!=nullptr)//遍历找到所有孩子中最大的高度
    {
        int NodeHeiht=GetNodeHeight(travePoint);//递归计算子节点高度
        MaxHeight=MaxHeight>NodeHeiht?MaxHeight:NodeHeiht;//找到最大节点
        travePoint=travePoint->nextSbling;
    }
    return MaxHeight+1;//我的高度为最大孩子高度加一
}

void LinkTree::GetNodeSize(TreeNode *node,int &count)
{
    if(node==nullptr)
        return ;
   count++;
   GetNodeSize(node->firstChild,count);
   GetNodeSize(node->nextSbling,count);

}

void LinkTree::GetleafSize(TreeNode *node, int &count)
{
    if(node==nullptr)
        return;
    if(node->firstChild==nullptr)
        count++;
    GetleafSize(node->firstChild,count);
    GetleafSize(node->nextSbling,count);
}
